// THIS IS THE PROVIDED CODE FOR PROGRAM #2, DSA 1, SPRING 2008

#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <string>
#include <ctime>

using namespace std;

// A simple class; each object holds five integer values and one string
class Data {
private:
  vector<int> values;
  string code;
public:
  Data() { values.resize(numValues); }
  static const int numValues = 5;
  void setValue(int i, int v) { values.at(i) = v; }
  int getValue(int i) { return values.at(i); }
  void setCode(string s) { code = s; }
  string getCode() { return code; }
};

// Load the data from a specified input file
void loadDataList(list<Data *> &l) {
  string filename;
  cout << "Enter name of input file: ";
  cin >> filename;

  ifstream input(filename.c_str());
  if (!input) {
    cerr << "Error: could not open " << filename << endl;
    exit(1);
  }

  // The first line indicates the size
  int size;
  input >> size;

  // Load the data
  for (int i = 0; i < size; i++) {
    Data *pData = new Data();
    for (int j = 0; j < Data::numValues; j++) {
      int v;
      input >> v;
      pData->setValue(j, v);
    }
    string s;
    input >> s;
    pData->setCode(s);
    l.push_back(pData);
  }

  input.close();
}

// Output the data to a specified input file
void writeDataList(const list<Data *> &l) {
  string filename;
  cout << "Enter name of output file: ";
  cin >> filename;

  ofstream output(filename.c_str());
  if (!output) {
    cerr << "Error: could not open " << filename << endl;
    exit(1);
  }

  // Write the size first
  int size = l.size();
  output << size << endl;

  // Write the data
  for (list<Data *>::const_iterator ipD = l.begin(); ipD != l.end(); ipD++) {
    for (int j = 0; j < Data::numValues; j++) {
      output << (*ipD)->getValue(j) << " ";
    }
    output << (*ipD)->getCode() << endl;
  }

  output.close();
}

void sortDataList(list<Data *> &);

// The main function calls routines to get the data, sort the data,
// and output the data.  The sort is timed according to CPU time.
int main() {
  list<Data *> theList;
  loadDataList(theList);

  cout << "Data loaded.  Executing sort..." << endl;

  clock_t t1 = clock();
  sortDataList(theList);
  clock_t t2 = clock();
  double timeDiff = ((double) (t2 - t1)) / CLOCKS_PER_SEC;

  cout << "Sort finished. CPU time was " << timeDiff << " seconds." << endl;

  writeDataList(theList);
}

// -------------------------------------------------
// YOU MAY NOT CHANGE OR ADD ANY CODE ABOVE HERE !!!
// -------------------------------------------------
#include <math.h>

list<Data*>::iterator get_element_at_index(int index, list<Data *> &l);

void mergesort(list<Data *> &l, int first, int last);
void merge(list<Data *> &l, int leftfirst, int leftlast, int rightfirst, int rightlast);

void compare(list<Data*>::iterator &leftfirst_itr,list<Data*>::iterator &rightfirst_itr,int pos,int &leftfirst, int &rightfirst,int index2);
Data *temparray[99167];
//**************************************************
//MERGE SORT
//**************************************************

void sortDataList(list<Data *> &l) {
	//list<Data *>::iterator itr;
	/*for(int i=0; i < 10000; i++){
		itr = get_element_at_index(i,l);
	}*/
	//cout <<(*itr)->getValue(1)<<endl;
	
	mergesort(l,1,l.size());
}

void mergesort(list<Data *> &l, int first, int last){
	if(first < last){
		//cout <<"mergesort"<<endl;
		//cout <<first<<"--"<<last<<endl;
		int mid = (first + last)/2;
		
		mergesort(l,first,mid);
		mergesort(l,mid+1,last);
		merge(l,first,mid,mid+1,last);
	}
}

void merge(list<Data *> &l, int leftfirst, int leftlast, int rightfirst, int rightlast){
	//cout <<"merge"<<leftfirst<<"-"<<leftlast<<"-"<<rightfirst<<"-"<<rightlast<<endl;
	int index2 = leftfirst-1;
	int start = leftfirst;
	
	list<Data *>::iterator leftfirst_itr = get_element_at_index(leftfirst,l);
	list<Data *>::iterator rightfirst_itr = get_element_at_index(rightfirst,l);
	
	//cout<<"::"<<endl;
	//cout <<(*leftfirst_itr)->getValue(0)<<"@@"<<(*rightfirst_itr)->getValue(0)<<endl;
	while((leftfirst <= leftlast) && (rightfirst <= rightlast)){
		compare(leftfirst_itr,rightfirst_itr,0,leftfirst,rightfirst,index2);
		index2++;
	}
	while(leftfirst <= leftlast){
		//cout<<"copyleft"<<endl;
		temparray[index2] = (*leftfirst_itr);
		leftfirst_itr++;
		leftfirst++;
		index2++;
	}
	while(rightfirst <= rightlast){
		//cout<<"copyright"<<endl;
		temparray[index2] = (*rightfirst_itr);
		rightfirst_itr++;
		rightfirst++;
		index2++;
	}
	
	list<Data*>::iterator itr=get_element_at_index(start,l);
	for(int index = (start-1); index < rightlast; index++){
		//cout <<index<<"~~";
		(*itr)=temparray[index];
		//cout<<temparray[index]->getValue(0);
		itr++;
	}
	//cout <<endl;
}

void compare(list<Data*>::iterator &leftfirst_itr,list<Data*>::iterator &rightfirst_itr,int pos,int &leftfirst, int &rightfirst,int index2){
	//cout <<"compare";
	//cout <<index2<<"**"<<endl;
	if((*leftfirst_itr)->getValue(pos) < (*rightfirst_itr)->getValue(pos)){
		temparray[index2] = (*leftfirst_itr);
		//cout<<(*leftfirst_itr)->getValue(0)<<"+"<<temparray[index2]->getValue(0);
		leftfirst_itr++;
		leftfirst++;
	}else if((*leftfirst_itr)->getValue(pos) > (*rightfirst_itr)->getValue(pos)){
		temparray[index2] = (*rightfirst_itr);
		//cout<<(*rightfirst_itr)->getValue(0)<<"+"<<temparray[index2]->getValue(0);
		rightfirst_itr++;
		rightfirst++;
	}else{
		if(pos == 4){
			temparray[index2] = (*leftfirst_itr);
			leftfirst_itr++;
			leftfirst++;
		}else{
			pos++;
			compare(leftfirst_itr,rightfirst_itr,pos,leftfirst,rightfirst,index2);
		}
	}
	//cout<<endl;
}

list<Data*>::iterator get_element_at_index(int index, list<Data *> &l){
	list<Data *>::iterator itr;
	itr = l.begin();
	//cout <<"==>"<<(*itr)->getValue(0)<<endl;
	int ctr;
	
	for(ctr=0; ctr < index; ctr++){
		//cout <<ctr<<"==>"<<(*itr)->getValue(1)<<endl;
		itr++;
	}
	//since the iterator is ahead of the ctr 
	itr--;
	//cout <<ctr<<"==>"<<(*itr)->getValue(0)<<endl;
	return itr;
}







//**************************************************
//BUBBLE SORT
//**************************************************

// You may add functions or class defintions here if you wish
/*void swap(Data *item1, Data *item2);

void sortDataList(list<Data *> &l) {
  // Fill in this function
	list<Data *>::iterator itr;
	itr = l.begin();
	
	int current=0;
	int numvalues = l.size();
	while(current < numvalues){
		for(int i=current; i < (numvalues-1); i++){
			Data *temp1 = (*itr++);
			Data *temp2 = (*itr);
			if((temp1->getValue(0)) > (temp2->getValue(0))){
				swap(*temp1,*temp2);
			}
			if((temp1->getValue(0)) == (temp2->getValue(0))){
				if((temp1->getValue(1)) > (temp2->getValue(1)))
					swap(*temp1,*temp2);
				if((temp1->getValue(1)) == (temp2->getValue(1))){
					if((temp1->getValue(2)) > (temp2->getValue(2)))
						swap(*temp1,*temp2);
					if((temp1->getValue(2)) == (temp2->getValue(2))){
						if((temp1->getValue(3)) > (temp2->getValue(3)))
							swap(*temp1,*temp2);
						if((temp1->getValue(3)) == (temp2->getValue(3))){
							if((temp1->getValue(4)) > (temp2->getValue(4)))
								swap(*temp1,*temp2);
						}		
					}	
				}	
			}
			
		}
		itr=l.begin();
		numvalues--;
	}
	
}

void swap(Data &item1, Data &item2){
	Data temp;
	temp = item1;
	item1  = item2;
	item2= temp;
	
}*/








